Search for: All records

We present quantum algorithms for sampling from possibly non-logconcave probability distributions expressed as 𝜋(𝑥)∝exp(−𝛽𝑓(𝑥)) as well as quantum algorithms for estimating the partition function for such distributions. We also incorporate a stochastic gradient oracle that implements the quantum walk operators inexactly by only using mini-batch gradients when 𝑓 can be written as a finite sum. One challenge of quantizing the resulting Markov chains is that they do not satisfy the detailed balance condition in general. Consequently, the mixing time of the algorithm cannot be expressed in terms of the spectral gap of the transition density matrix, making the quantum algorithms nontrivial to analyze. We overcame these challenges by first building a reference reversible Markov chain that converges to the target distribution, then controlling the discrepancy between our algorithm’s output and the target distribution by using the reference Markov chain as a bridge to establish the total complexity. Our quantum algorithms exhibit polynomial speedups in terms of dimension or precision dependencies when compared to best-known classical algorithms under similar assumptions. 

A promising avenue for the preparation of Gibbs states on a quantum computer is to simulate the physical thermalization process. The Davies generator describes the dynamics of an open quantum system that is in contact with a heat bath. Crucially, it does not require simulation of the heat bath itself, only the system we hope to thermalize. Using the state-of-the-art techniques for quantum simulation of the Lindblad equation, we devise a technique for the preparation of Gibbs states via thermalization as specified by the Davies generator.In doing so, we encounter a severe technical challenge: implementation of the Davies generator demands the ability to estimate the energy of the system unambiguously. That is, each energy of the system must be deterministically mapped to a unique estimate. Previous work showed that this is only possible if the system satisfies an unphysical 'rounding promise' assumption. We solve this problem by engineering a random ensemble of rounding promises that simultaneously solves three problems: First, each rounding promise admits preparation of a 'promised' thermal state via a Davies generator. Second, these Davies generators have a similar mixing time as the ideal Davies generator. Third, the average of these promised thermal states approximates the ideal thermal state. 

Abstract BackgroundOropharyngeal cancer (OPC) exhibits varying responses to chemoradiation therapy, making treatment outcome prediction challenging. Traditional imaging‐based methods often fail to capture the spatial heterogeneity within tumors, which influences treatment resistance and disease progression. Advances in modeling techniques allow for more nuanced analysis of this heterogeneity, identifying distinct tumor regions, or habitats, that drive patient outcomes. PurposeTo interrogate the association between treatment‐induced changes in spatial heterogeneity and chemoradiation resistance of oropharyngeal cancer (OPC) based on a novel tumor habitat analysis. MethodsA mathematical model was used to estimate tumor time dynamics of patients with OPC based on the applied analysis of partial differential equations. The position and momentum of each voxel was propagated according to Fokker‐Planck dynamics, that is, a common model in statistical mechanics. The boundary conditions of the Fokker‐Planck equation were solved based on pre‐ and intra‐treatment (i.e., after 2 weeks of therapy)¹⁸F‐FDG‐PET SUV images of patients (n = 56) undergoing definitive (chemo)radiation for OPC as part of a previously conducted prospective clinical trial. Tumor‐specific time dynamics, measured based on the solution of the Fokker‐Planck equation, were generated for each patient. Tumor habitats (i.e., non‐overlapping subregions of the primary tumor) were identified by measuring vector similarity in voxel‐level time dynamics through a fuzzy c‐means clustering algorithm. The robustness of our habitat construction method was quantified using a mean silhouette metric to measure intra‐habitat variability. Fifty‐four habitat‐specific radiomic texture features were extracted from pre‐treatment SUV images and normalized by habitat volume. Univariate Kaplan‐Meier analyses were implemented as a feature selection method, where statistically significant features (p < 0.05, log‐rank) were used to construct a multivariate Cox proportional‐hazards model. Parameters from the resulting Cox model were then used to construct a risk score for each patient, based on habitat‐specific radiomic expression. The patient cohort was stratified by median risk score value and association with recurrence‐free survival (RFS) was evaluated via log‐rank tests. ResultsDynamic tumor habitat analysis partitioned the gross disease of each patient into three spatial subregions. Voxels within each habitat suggested differential response rates in different compartments of the tumor. The minimum mean silhouette value was 0.57 and maximum mean silhouette value was 0.8, where values above 0.7 indicated strong intra‐habitat consistency and values between 0.5 and 0.7 indicated reasonable intra‐habitat consistency. Nine radiomic texture features (three GLRLM, two GLCOM, and three GLSZM) and SUVmax were found to be prognostically significant and were used to build the multivariate Cox model. The resulting risk score was associated with RFS (p = 0.032). By contrast, potential confounding factors (primary tumor volume and mean SUV) were not significantly associated with RFS (p = 0.286 andp = 0.231, respectively). ConclusionWe interrogated spatial heterogeneity of oropharyngeal tumors through the application of a novel algorithm to identify spatial habitats on SUV images. Our habitat construction technique was shown to be robust and habitat‐specific feature spaces revealed distinct underlying radiomic expression patterns. Radiomic features were extracted from dynamic habitats and used to build a risk score which demonstrated prognostic value. 

Abstract BackgroundDelta radiomics is a high‐throughput computational technique used to describe quantitative changes in serial, time‐series imaging by considering the relative change in radiomic features of images extracted at two distinct time points. Recent work has demonstrated a lack of prognostic signal of radiomic features extracted using this technique. We hypothesize that this lack of signal is due to the fundamental assumptions made when extracting features via delta radiomics, and that other methods should be investigated. PurposeThe purpose of this work was to show a proof‐of‐concept of a new radiomics paradigm for sparse, time‐series imaging data, where features are extracted from a spatial‐temporal manifold modeling the time evolution between images, and to assess the prognostic value on patients with oropharyngeal cancer (OPC). MethodsTo accomplish this, we developed an algorithm to mathematically describe the relationship between two images acquired at time and . These images serve as boundary conditions of a partial differential equation describing the transition from one image to the other. To solve this equation, we propagate the position and momentum of each voxel according to Fokker–Planck dynamics (i.e., a technique common in statistical mechanics). This transformation is driven by an underlying potential force uniquely determined by the equilibrium image. The solution generates a spatial‐temporal manifold (3 spatial dimensions + time) from which we define dynamic radiomic features. First, our approach was numerically verified by stochastically sampling dynamic Gaussian processes of monotonically decreasing noise. The transformation from high to low noise was compared between our Fokker–Planck estimation and simulated ground‐truth. To demonstrate feasibility and clinical impact, we applied our approach to¹⁸F‐FDG‐PET images to estimate early metabolic response of patients (n = 57) undergoing definitive (chemo)radiation for OPC. Images were acquired pre‐treatment and 2‐weeks intra‐treatment (after 20 Gy). Dynamic radiomic features capturing changes in texture and morphology were then extracted. Patients were partitioned into two groups based on similar dynamic radiomic feature expression via k‐means clustering and compared by Kaplan–Meier analyses with log‐rank tests (p < 0.05). These results were compared to conventional delta radiomics to test the added value of our approach. ResultsNumerical results confirmed our technique can recover image noise characteristics given sparse input data as boundary conditions. Our technique was able to model tumor shrinkage and metabolic response. While no delta radiomics features proved prognostic, Kaplan–Meier analyses identified nine significant dynamic radiomic features. The most significant feature was Gray‐Level‐Size‐Zone‐Matrix gray‐level variance (p = 0.011), which demonstrated prognostic improvement over its corresponding delta radiomic feature (p = 0.722). ConclusionsWe developed, verified, and demonstrated the prognostic value of a novel, physics‐based radiomics approach over conventional delta radiomics via data assimilation of quantitative imaging and differential equations. 

Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of ann-dimensional convex body within multiplicative error ε usingÕ(n³+ n^2.5/ε) queries to a membership oracle andÕ(n⁵+n^4.5/ε)additional arithmetic operations. For comparison, the best known classical algorithm usesÕ(n^3.5+n³/ε²)queries andÕ(n^5.5+n⁵/ε²)additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of “Chebyshev cooling,” where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error. To complement our quantum algorithms, we also prove that volume estimation requiresΩ (√ n+1/ε)quantum membership queries, which rules out the possibility of exponential quantum speedup innand shows optimality of our algorithm in 1/ε up to poly-logarithmic factors. 

We present an efficient quantum algorithm for simulating the dynamics of Markovian open quantum systems. The performance of our algorithm is similar to the previous state-of-the-art quantum algorithm, i.e., it scales linearly in evolution time and poly-logarithmically in inverse precision. However, our algorithm is conceptually cleaner, and it only uses simple quantum primitives without compressed encoding. Our approach is based on a novel mathematical treatment of the evolution map, which involves a higher-order series expansion based on Duhamel’s principle and approximating multiple integrals using scaled Gaussian quadrature. Our method easily generalizes to simulating quantum dynamics with time-dependent Lindbladians. Furthermore, our method of approximating multiple integrals using scaled Gaussian quadrature could potentially be used to produce a more efficient approximation of time-ordered integrals, and therefore can simplify existing quantum algorithms for simulating time-dependent Hamiltonians based on a truncated Dyson series.